package com.atguigu.binaryTree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode parent;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
          this.right = right;
      }
  }

public class preOrder {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> ret=new ArrayList<>();
            Stack<TreeNode> stack=new Stack<>();
            TreeNode cur=root;
            while(cur!=null || !stack.isEmpty()){
                //剩下左路节点的右子树还没遍历
                while(cur!=null){
                    ret.add(cur.val);
                    stack.push(cur);
                    cur=cur.left;
                }
                cur=stack.pop();
                cur=cur.right;
            }
            return ret;
    }
}
